This invention relates to an improvement in a constraint condition evaluation method and a constraint condition evaluation system which check if there is a conflict in the constraint conditions in the layout of components such as those on an IC.
When component layouts in ICs and others must be modified under some given constraints, one known method: is used; in that method, the constraint conditions are represented by a directed graph called constraint graph and, based on this graph, the check is made to see if there are conflicts in the constraint conditions. FIG. 14 shows an example of a constraint graph. As shown in this figure, a constraint graph, usually composed of edges connecting a plurality of vertexes (v), starts with a initial vertex called a source and ends with an terminal vertex called a sink. In this figure, a vertex is represented by a circle-shaped symbol, and an edge by an arrow-shaped symbol.
In a constraint graph, there are paths from the source to other vertexes. Each vertex usually represents the base point of a component to be laid out, and the position of the vertex X(v) represents the position of the base point of each component to be laid out. An edge between two vertexes has a numeric value called a weight. The weight of each edge represents an necessary interval or space required for both base points between elements to be laid out.
For example, FIG. 15 is an example of component layout corresponding to the constraint graph in FIG. 14. This figure shows how components A, B, and C are laid out along the X axis. The constraint condition in this example is that a space of 2 or larger is required between each two components.
The positions of components A, B, and C are represented by X(va), X(vb), and X(vc), respectively, based on the leftmost points, va, vb, and vc. FIG. 15 corresponds to the constraint condition. More specifically, the weight of 13 between vertexes va and vb indicates that the total width of 13, consisting of the width (11) of a part of component A and the space of 2, is required between the left end of component A and the left end of component B. Similarly, the weight of 12 between vertexes vb and vc indicates that the total width of 12, consisting of the width (10) of component B and the space of 2, is required between the left end of component B and left end of component. C.
A constraint graph normally contains a back edge whose initial vertex is smaller than that of the terminal vertex. Typically, a back edge has a negative weight. In FIG. 14, a back edge goes from vertex vc to vertex va, and the weight of -22 of this back edge indicates that the left end of component A is at most 22 left of the left end of component C. This is because the distance from the left end of component A to the right end of break of component A where component C is to be placed is 32 (11+21) and because the component C requires the length of 10 consisting of the width of 8 and the space of 2 on the right side. As a result, only the length of 22 is allowed.
In general, when the edge e .mu. .nu. is directed from the first vertex v .mu. to the second vertex v .nu. and when the edge e .mu. .nu. has the weight of W(e .mu. .nu.), the position X(v .nu.) of point v .nu. must be placed at least W(e .mu. .nu.) positions right of X(v .mu.). This relationship is represented by the following formula:
[Formula 1] EQU X(v .nu.).gtoreq.X(v .mu.)+W(e .mu. .nu.)
A constraint graph usually contains a cycle. A cycle, whose paths can be followed in the direction, has at least one back edge. The weight of a back edge indicates an space within which each component is to be placed. If the sum of the weights of the paths going from the terminal vertex of a back edge to the initial vertex is not superior to the weight of the back edge, each component may be placed within the space indicated by the back edge. Here, the sum of the weights of the paths going from the terminal vertex of a back edge to the initial vertex does not exceed the weight of the back edge, means the sum of the weight of the cycle is negative. Of course, when the sign of each weight is reversed, the sum is positive.
If the sum of the weights of the forward edges does not exceed the weight of the back edge or not is determined simply by adding up all the weights in the cycle. If the result is positive, the cycle is called a Positive Cycle (PC) and it is known that there is no solution for the constraint indicated by the PC (Reference 1: Y. E. Cho: A Subjective Review of Compaction, Proc. 22nd Design Automation Conference, 1985, pp. 396-404../Reference 2: K. Ishima, S. Tsukiyama: On an Algorithm to Detect Positive Cycle in a Constraint Graph for Layout Compaction, IEICE Trans. Vol. E 74, No. 11 November 1991, pp. 3613-3616).
For example, in FIG. 15, the width of said break is 21 and components B and C require the total width 24 of width of themselves 10+8=18 and spaces 2.times.3=6. Then break width is 3 less than the required width, therefore, it is impossible to lay out the components so that they satisfy the condition. This is confirmed simply by adding up the weights contained in the cycle on the constraint graph without having to lay out components. That is, in FIG. 14, because the sum of the weights contained in the cycle is calculated as
[Formula 2] EQU 13+12-22=3&gt;0
and because this cycle is PC and the space is 3 less than the desired value, it is determined that there is no solution that satisfies the constraint condition.
Such a PC in a constraint graph must be dissolved and removed from the graph prior to the layout operation. The evaluation of a conflict in a constraint graph means to detect and remove such a PC. Detecting a PC with the use of a constraint graph is especially advantageous when the components relationship becomes complicated as the number and types of components increase.
The following is an example in which a PC is detected in a constraint graph. First, this method sorts the vertexes according to some criteria. Because a back edge is defined as an edge whose initial vertex is larger than the terminal vertex in the sort sequence, at least one edge is a back edge in a cycle. In particular, when the vertexes are sorted in ascending order according to their positions X(v), the number of back edges b is much less than the total number of edges in the graph. Therefore, investigating only the paths containing back edges efficiently finds cycles in a constraint graph.
In a prior art, this is used to reduce the time to detect PCs (Reference 2 shown above/Reference 3: J. Do, W. Dawson: SPACER II: A Well Behaved IC layout Compactor, Proceedings of VLSI 85 International Conference, 1985.).
This method is described more in detail. First, all back edges fi (i=1, . . . b) are removed from the constraint graph G, and the resulting back-edge-removed graph is defined as G0.
[Formula 3] EQU G0=G-{f1, f2, . . . , fb}
If G0 is unconnected, a minimum number of back edges are added to form G0, and added back edges are removed from the back edge set. Note that, when the back edge set is null (b=0), there is no PC in the constraint graph, so this method immediately ends processing.
Starting from the back-edge-removed graph G0, this method repeats the following processing for each back edge fi in order of i=1, . . . , b. First, the method adds the back edge fi to the graph Gi-1 to form the graph Gi-1+fi and, from this graph, detects a PC. When a PC is detected, the method records it in the specified memory area. Then it removes the back edge fi from the graph Gi-1+fi again to form the graph Gi-1 and regards the graph Gi-1 as the next graph Gi for use in the next back edge processing. On the other hand, when the back edge fi is added but no PC is detected, this method uses the graph Gi-1+fi as Gi, with the back edge fi still added, for the next back edge processing.
In repeating the above procedure, the initial graph G0 contains no PC because it contains no back edge. When the PC is detected in the graph Gi-1+fi, the back edge fi is re-detected. Therefore, the next graph Gi that is used for the next back edge fi+1 also contains no PC. After this procedure is repeated, all the detected PCs are recorded in the specified memory area. A resultant graph Gb becomes the constraint graph G from which all the back edges constituting the PCs have been removed.
If no PC was found while the procedure for each back edge fi (i=1, . . . , b) was repeated, all the back edges fi are added again to the back-edge-removed graph G0 and, therefore, Gb=G0.
FIG. 16 is a flowchart showing an example in which PCs are detected according to the prior art. For the graph Gi at a given vertex, the longest path length between two vertexes, v .mu. and v .nu., in the graph Gi is represented as Li (v .mu., v .nu.). Among them, the longest path length from the source to the vertex v .mu. is represented as Li (v .mu.).
In the processing shown in FIG. 16, the procedure finds the longest path length L0 (v .lambda.) from the source to a vertex v .lambda. in the back-edge-removed graph G0 (step 151). Next, the procedure sequentially selects all the back edges fi (i=1, . . . , b) while incrementing i from 1 to b (steps 152 and 153) and does the following processing for each back edge fi. In the following discussion, the initial vertex of the back edge fi is defined as v .mu., and the terminal vertex as v .nu..
First, the procedure determines that the back edge fi does not form a PC if the difference between the longest path length Li-1 (v .nu.) from the source to the terminal vertex v .nu. of the back edge fi and the longest path length Li-1 (v .mu.) from the source to the initial vertex v .mu. of the back edge fi does not exceed the weight W(Fi) of the back edge fi (step 154). That is, if the following is satisfied,
[Formula 4] EQU Li-1(v .nu.).gtoreq.Li-1(v .mu.)+W(fi)
then, the back edge fi does not form a PC.
Theoretically, it is simple to determine whether or not a PC is formed, using the relationship between the longest path length Li-1 (v .mu., v .nu.) from initial vertex v .mu. to the terminal vertex v .nu. and the weight W(fi) of the back edge fi. The following formula is used to determine whether or not a PC is formed:
[Formula 5] EQU 0.gtoreq.Li-1(v .nu., v .mu.)+W(fi)
Here, it should be noted that the longest path length Li-1 (v .mu.) from the source to the initial vertex v .mu. is equal to or larger than the sum of the longest path length Li-1 (v .nu.) from the source to the terminal vertex v .nu. and the longest path length Li-1 (v .nu., v .mu.) from the terminal vertex v .nu. to the initial vertex v .mu..
[Formula 6] EQU Li-1(v .mu.).gtoreq.Li-1(v .nu.)+Li-1(v .nu., v .mu.)
By transposing the formula;
[Formula 7] EQU Li-1(v .mu.)-Li-1(v .nu.).gtoreq.Li-1(v .nu., v .mu.)
By transposing formula 4;
[Formula 8] EQU 0.gtoreq.Li-1(v .mu.)-Li-1(v .nu.)+W(fi)
In the above formula, Li-1(v .mu.)-Li-1(v .nu.) may be replaced by the left hand side of formula 7. This results in formula 5, meaning that formula 4 may be used to determine whether or not a PC is present. So, using the difference between the longest path length Li-1 (v .nu.) from source to the terminal vertex v .nu. of the back edge fi and the longest path length Li-1(v .mu.) from the source to the initial vertex V .mu. of the back edge fi eliminates the need to find the longest path length Li-1 (v .nu., v .mu.) between the initial vertex v .mu. and the terminal vertex v .nu. of the back edge fi. This speeds up processing.
In step 154, if the back edge fi does not form a PC, the procedure uses the following formula by adding the back edge fi to the graph (step 155):
[Formula 9] EQU Gi=Gi-1+fi
The longest path length Li-1 (v .lambda.) from the source to any given vertex v .lambda. is the same. So, the longest path length Li-1 (v .lambda.) is used also for the processing of the next back edge fi+1.
[Formula 10] EQU Li(v .lambda.)=Li-1(v .lambda.)
Then, the next back edge is selected (step 152).
On the other hand, in step 154, if
[Formula 11] EQU Li-1(v .nu.)&lt;Li-1(v .mu.)+W(fi)
then a check is made to see if the terminal vertex v .nu. is on the longest path from the source to the initial vertex v .mu. (step 156). If the terminal vertex v .nu. is on the longest path from the source to the initial vertex v .mu., the sum of the back edge fi and the path from the terminal vertex v .nu. to the initial vertex v .mu. form a PC. So, they are recorded as a PC (step 157). In this case, the procedure keeps the graph and the positions of the vertexes unchanged:
[Formula 12] EQU Gi=Gi-1 EQU Li(v .lambda.)=Li-1(v .lambda.)
and selects the next back edge (step 152).
If, in step 156, the terminal vertex v .nu. is not on the longest path from the source to the initial vertex v .mu., the procedure goes to the step 158 and the following steps. That is, for all the vertexes v .lambda. to which the paths from the terminal vertex v .nu. in the graph exist, the procedure finds the longest path length Li-1 (v .nu., v .lambda.) from the terminal vertex v .nu. of the back edge (step 158). And if there is a path from this terminal vertex v .nu. to the initial vertex v .mu., and if Li-1(v .nu., v .mu.) is larger than the weight W (fi) of the back edge, that is, if
[Formula 13] EQU Li-1(v .nu., v .mu.)+W(fi).gtoreq.0
then (step 159), the sum of the longest path from the terminal vertex v .nu. to the initial vertex v .mu. and the back edge fi is recorded as a PC (step 157). And, the procedure keeps the graph and the positions of the vertexes unchanged:
[Formula 14] EQU Gi=Gi-1 EQU Li(v .lambda.)=Li-1(v .lambda.)
and selects the next (i=i+1) back edge (step 152).
On the other hand, in step 159, if the longest path length Li-1 (v .nu., v .mu.) does not exceed the weight W (fi) of the back edge,
[Formula 15] EQU Li-1(v .nu., v .mu.)+W(fi).ltoreq.0
or if there is no path from the terminal vertex v .nu. to the initial vertex v .mu., the back edge fi does not form a PC. In this case, the procedure adds the back edge fi to the graph (step 1510):
[Formula 16] EQU Gi=Gi-1+fi
As the result, a path which is through the added back edge becomes new one of paths from the source to each vertex. Thus, the longest path length from the source to each vertex is updated (step 1511). That is, a check is made to see if the longest path length via the added back edge is larger than the longest path length Li of the path from the source to each vertex. If the former is larger than the latter, the longest path length is replaced.
The longest path length of the path from the source via the back edge to each vertex v .lambda. is calculated by adding the weight W (fi) of the back edge and the longest path length Li-1 (v .nu., v .lambda.) of the path from the terminal vertex v .nu. of the back edge to the vertex v .lambda. to the longest path length Li-1(v .mu.) of the path from the source to the initial vertex v .mu. of the back edge fi. That is,
[Formula 17] EQU Li-1(v .mu.)+W(fi)+Li-1(v .mu., v .lambda.)
Let this be Li-1 X, and let max .oval-hollow. be a function which returns the maximum value, then said replacement is represented:
[Formula 18] EQU Li(v .lambda.)=max(Li-1(v .lambda.), Li-1 X)
Then, the procedure selects the next (i=i+1) back edge (step 152). In finding the longest path length Li (v) and Li (v .nu., v .mu.), the Dijkstra algorithm speeds up the processing.
To efficiently detect a PC, the procedure in FIG. 16 uses the difference between the longest path length Li-1 (v .nu.) of the path from the source to the terminal vertex v .nu. of the back edge fi and the longest path length Li-1(v .mu.) of the path from the source to the initial vertex v .mu. of the back edge fi. We can also use only the longest path length Li-1 (v .nu., v .mu.) of the path from the initial vertex v .mu. of the back edge fi to the terminal vertex v .nu. in order to detect a PC.
According to the prior art, most of the processing time is used for the calculation of longest paths. Because the calculation time of the longest path is O (n log n), the time needed for detecting a PC is O (bn log n). And, the number of back edges is generally proportional to the number of vertexes in the graph, meaning that the execution time is O (n.sup.2 log n) (See the Reference 1 described above). This indicates that the more and more time is required as the system scale becomes larger and larger. So, a constraint condition evaluation method and a constraint condition evaluation system which detect speedily the PCs in a constraint graph used in a large system have long been awaited.
This invention seeks to solve the problems associated with a prior art described above. It is an object of this invention to provide a constraint condition evaluation method and a constraint condition evaluation system which detect speedily the PCs in a constraint graph used in a large system.